#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 429. N 叉树的层序遍历.py
@time: 2022/2/21 16:04
@desc: https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
> 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

1. 用队列层序遍历， Ot(N), Os(N)
'''
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        if not root: return []
        queue, res = [[root]], []
        while queue:
            node_list = queue.pop(0)
            val_list = []
            for node in node_list:
                val_list.append(node.val)
            res.append(val_list)
            tmp = []
            for node in node_list:
                if not node.children: continue
                for child in node.children:
                    tmp.append(child)
            if tmp: queue.append(tmp)
        return res

if __name__ == '__main__':
    root = Node(1, children=[Node(3, children=[Node(5), Node(6)]), Node(2), Node(4)])
    res = Solution().levelOrder(root)
    print(res)